//这里我们学习数据压缩
//数据压缩很重要，并且实现起来较为简单。
//为了实现数据压缩，我们需要一些新的工具，也就是标准输入和输出的扩展，让我们能进行位级的输入输出处理
//不存在能压缩所有字符串的算法，两种证明方法
//一种是反证，如果存在这种算法，那么则一定也能压缩大小为1的字符串，那么就能给他压缩到0，这是不可能的
//另一种是考虑映射，他将一个更大的集合映射到更小的集合，因为计算机中的数学是离散的，这样的映射一定会是一对多的，那么则这样的算法一定会出现错误
//不要期待找到最好的压缩算法
//run-length encoding 游程编码
//有时候，流里是很长的一串0或很长的一串1，这样我们可以采用计数的方式进行存储，比如先用一个数字表示一串0的个数，再用一个数字表示一串1的个数这样。
//接口就两个，一个压缩，一个解压缩。
import edu.princeton.cs.algs4.BinaryStdIn;
import edu.princeton.cs.algs4.BinaryStdOut;
public class RunLength {
    private final static int R = 256;     //游程编码存储的最多个0或1的个数
    private final static int lgR = 8;     //所需游程编码的空间大小，以bite为单位

    //下面解压缩反过来就OK
    //读取输入，对输入进行计数，然后输出
    public static void compress()
    {
        char run = 0;
        boolean old = false;
        while (!BinaryStdIn.isEmpty()) {
            boolean b = BinaryStdIn.readBoolean();
            if (b != old) {
                BinaryStdOut.write(run, lgR);
                run = 1;
                old = !old;
            }
            else {
                if (run == R-1) {
                    BinaryStdOut.write(run, lgR);
                    run = 0;
                    BinaryStdOut.write(run, lgR);
                }
                run++;
            }
        }
        BinaryStdOut.write(run, lgR);
        BinaryStdOut.close();
    }

    //输入不为空，则从零开始输出，每次读取lgR个长度，输出其代表个数的0或1，然后修改下次输出为1或0
    public static void expand()
    {
        boolean bit=false;
        while(!BinaryStdIn.isEmpty())
        {
          int r=BinaryStdIn.readInt(lgR);
          for(int i=0;i<r;i++)
          {
            BinaryStdOut.write(bit);
          }
          bit=!bit;
        }
        BinaryStdOut.close();
    }

    
    public static void main(String[] args) throws Exception {
        System.out.println("Hello, World!");
    }
}
